#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 20 11:50:56 2019

@author: joshwalton
"""

"""
A Python module for the Othello game.
This is a game which 2 players play on a 8x8 board. Each player has their own pieces on the board. Players
take turns moving their pieces to empty positions on the board. After a move, any of the opponents pieces that are in
a straight line and bounded by the piece just placed and another piece of that players will change to the current players
symbol. The objective of the game is to have the majority of the pieces by the end of the game which will be 
when their are no valid moves left for either player.
"""

from copy import deepcopy
import numpy as np
import itertools
import random
def newGame(player1,player2): 
    """
    Parameters
    ----------
    player1 : Non-empty string corresponding to the desired name of player1
    player2 : Non-empty string corresponding to the desired name of player2

    Returns
    -------
    game : A new-game dictionary containing the names of both players, the value 'who' which corresponds
    to who will go first and a new game board.

    
    """
    
    game = {
        'player1' : player1, 
        'player2' : player2,
        'who' : 1,
        'board' : [[0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0],
                   [0,0,0,2,1,0,0,0],
                   [0,0,0,1,2,0,0,0],
                   [0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0]]
        }
    return game


def printBoard(board):
    """
    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there
    
    Returns
    -------
    Prints the board in a nicely formatted game-board with labelled axis

    """
    boardcopy = deepcopy(board) # creates copy of board
    letters = ['a','b','c','d','e','f','g','h']
    print(' ' + '|'+'|'.join(map(str,letters))+'|'+'\n'+ ' ' + '+-'*8+'+')  # prints the column labels seperated by a line    
    
    for rows in boardcopy:
        for n in range(8):            
            if rows[n]==0:
                rows[n]=' ' # creates empty tiles
            if rows[n]==1:
                rows[n]='X' # creates player 1's pieces
            if rows[n]==2:
                rows[n]='O' # creates player 2's pieces
    
    for n in range(8):
        boardcopy[n][0] = str(n+1) + '|' + str(boardcopy[n][0]) # numbers the rows 
        boardcopy[n][7] = str(boardcopy[n][7]) + '|' 

    for row in range(len(boardcopy)):
        print(*boardcopy[row], sep='|') # separates pieces with a line
    print(' ' + '+-'*8+'+') # last row 
    return board
   


def strToIndex(s):
    """

    Parameters
    ----------
    s : a string s of the form 'nX' or 'Xn' where:
        ~ n is a number from 1 to 8 corresponding to the row on the printed game-board
        ~ X is a letter in the alphabet from a to h corresponding to the column on the printed game-board
    
    Returns
    -------
    A tuple of the form (m,k) where:
        ~ m is a number from 0 to 7 corresponding to the row on the board
        ~ k is a number from 0 to 7 corresponding to the column on the board
    
    Raises
    ------
    ValueError : if s is not of the correct form.

    """
  
    
    try:     
        letters = ['a','b','c','d','e','f','g','h']
        numbers = list(range(1,9))       
        s = s.replace(" ","") # removes all spaces
        s = s.lower() # makes any capital letters lowercase
        yposition = int(''.join(x for x in s if x.isdigit())) # takes the integer part of the string    
        s = s.replace(str(yposition),'') # removes integer part of the string so it is now only a letter        
        return(numbers.index(yposition),letters.index(s))  
    except ValueError: # if s is of the wrong form
        print('Invalid Choice of Move!')
        s=input('Try again: ')   
        return strToIndex(s)

        
def indexToStr(t):
    """

    Parameters
    ----------
    t : a tuple of the form (n,k) where:
        ~ n is a number between 0 and 7 corresponding to the row on the board
        ~ k is a number between 0 and 7 corresponding to the column on the board
    
    Returns
    -------
    A non-empty string of the form 'Xn' where:
        ~ n is a number from 1 to 8 corresponding to the row on the printed game-board
        ~ X is a letter in the alphabet from a to h corresponding to the column on the printed game-board

    
    """

    letters = ['a','b','c','d','e','f','g','h']
    numbers = list(range(1,9))
    return str(letters[t[1]]+str(numbers[t[0]])) # converts t to a string representing a game-board co-ordinate

def loadGame():
   """
    Attempts to load a file 'game.txt' which contains values for the names of both players, 
    whose turn it is and the board.
    
    Returns
    -------
    game : a dictionary containing the information stored in the file where the first 2 lines
    are the names of the players, the 3rd line corresponds to whose go it is and lines 4-12 is the board.
    
    Raises
    ------
    ValueError : if the format of the file is not correct / the values within it are not valid.
    FileNotFoundError : if the file cannot be loaded.
    
   """
    
   try:
        with open('game.txt') as f: # loads game file
            content = f.readlines() # reads each line in file into a list    
            content = [x.rstrip() for x in content] # removes whitespace at end of each string
            board = []
            try:
                for el in content[3:]:
                    el = [int(s) for s in el.split(',')] # takes integers that are separated by commas
                    board.append(el) # makes up the board
            except ValueError: # if board not in correct form
                raise ValueError('Your file is not of the correct form')
       
        if int(content[2]) not in [1,2] or content[0] == '' or content[1] == '' or len(board) != 8: #checks to see if names, who and board is valid
            raise ValueError  
        for n,k in itertools.product(range(8), range(8)):
            if board[n][k] not in [0,1,2] or len(board[n]) != 8: # checks each individual value in the board and each list
                raise ValueError('Your file is not of the correct form')
        
           
            game = {'player1' : content[0] ,                     
                    'player2' : content[1] ,
                    'who' : content[2],
                    'board' : board}
        return game
        
        
            
   except FileNotFoundError: # if file can't be loaded
        raise FileNotFoundError('Error: The game file cannot be loaded')
        
            


def getLine(board,who,pos,dir):
    """

    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there
    
    who : Has the value 1 or 2 dependent on if it is player 1's or player 2's turn respectively
    
    pos : A tuple of the form (m,k) that represents a position on the board where:
        ~ m is a number from 0 to 7 corresponding to the row on the board
        ~ k is a number from 0 to 7 corresponding to the column on the board
    
    dir : A tuple where each value is either 0, 1 or -1. If one of the values is 0, it means that
    the row/column number does not change. If one of the values is 1 or -1, the row/column number will
    increase/decrease respectively.
    
    Returns
    -------
    pieces : A list of tuples that corresponds to where the opponents pieces are on the board in a continuous straight line 
    that starts from the position 'pos' in the direction 'dir' and ends with a piece of the current player 'who'.
    If there is no such line, an empty list is returned.
    
    Raises
    ------
    ValueError : If there is no continuous line of opponents pieces that ends with the current players piece.
    IndexError : If the straight line starting from 'pos' in the direction 'dir' starts with 0 or the current players piece 'who'.
    
    """
    tilesincolumn = []
    tilesinrow = []
    pieces = []
    tilesfrompos = []
    upperdiagonals = []
    lowerdiagonals = []
    upperdiagonals2 = []
    lowerdiagonals2 = []
    
    if dir == (0,-1):
        for n in range(pos[1]):
            tilesfrompos.append(board[pos[0]][n]) # pieces in that row from 'pos'
        try: 
            last1 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(1)  # position of the last 1
            last2 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(2)            
            if tilesfrompos[-1] == who or tilesfrompos[-1] == 0: return []                                     
        except ValueError or IndexError: return [] # if player has no piece on that row or if there is no continuous line         
        
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i > last1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i > last2]
        
        for el in indices2:     
            if who == 1 and set(tilesfrompos[last1+1:]) == {2}: # check line is continuous
                pieces.append((pos[0],el)) 
            if who == 2 and set(tilesfrompos[last2+1:]) == {1}:
                pieces.append((pos[0],el))
                
                
    if dir == (0,1):
        for n in range(8): 
            tilesinrow.append(board[pos[0]][n])
        for k in range(pos[1]+1,8): 
            tilesfrompos.append(board[pos[0]][k])
        try:
            first1 = tilesfrompos.index(1) 
            first2 = tilesfrompos.index(2)                       
            if tilesfrompos[0] == who or tilesfrompos[0] == 0: return []
        except ValueError or IndexError: return []        
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i < first1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i < first2]      
        for el in indices2:               
            if who == 1 and set(tilesfrompos[0:first1]) == {2}:
                pieces.append((pos[0],el+(len(tilesinrow)-len(tilesfrompos))))
            if who == 2 and set(tilesfrompos[0:first2]) == {1}:
                pieces.append((pos[0],el+(len(tilesinrow)-len(tilesfrompos))))
    
    if dir == (1,0): 
        for k in range(pos[0]+1,8):
            tilesfrompos.append(board[k][pos[1]])
        try:
            first1 = tilesfrompos.index(1)
            first2 = tilesfrompos.index(2)
            if tilesfrompos[0] == 0 or tilesfrompos[0] == who: return []
        except ValueError or IndexError: return []        
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i < first1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i < first2]  
        for el in indices2:               
            if (who == 1 and set(tilesfrompos[0:first1]) == {2}) or (who == 2 and set(tilesfrompos[0:first2]) == {1}):
                pieces.append(((el+8-len(tilesfrompos)), pos[1]))
            
                    
    if dir == (-1,0):
        for n in range(8):
            tilesincolumn.append(board[n][pos[1]])
        tilesfrompos = tilesincolumn[0:pos[0]]        
        try:
            last1 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(1)
            last2 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(2)
            if tilesfrompos[-1] == 0 or tilesfrompos[-1] == who: return []
        except ValueError or IndexError: return []
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i > last1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i > last2]        
        cols = []
        rows = []
        for l in range(1,len(indices2)+1): 
            cols.append(pos[1])             
        for n in range(1,len(indices2)+1):    
            if who == 1 and set(tilesfrompos[last1+1:]) == {2}:
                rows.append(pos[0]-n) 
            if who == 2 and set(tilesfrompos[last2+1:]) == {1}:
                rows.append(pos[0]-n)             
        pieces = list(zip(rows, cols))
    
    for offset in range(8):               
        diagsupper = [ row[i+offset] for i,row in enumerate(board) if 0 <= i+offset < len(row)]            
        upperdiagonals.append(diagsupper)            
        diagslower = [ row[i-offset] for i,row in enumerate(board) if 0 <= i-offset < len(row)]            
        lowerdiagonals.append(diagslower)            
    maindiag = upperdiagonals[0]
    del upperdiagonals[0]
    del lowerdiagonals[0]           
    n = abs(pos[0]-pos[1])
    
    if dir == (-1,-1): 
        if pos[0] > pos[1]:
            diag = lowerdiagonals[n-1] 
            tilesfrompos = diag[0:pos[1]]   
        if pos[0] < pos[1]:
            diag = upperdiagonals[n-1]
            tilesfrompos = diag[0:pos[0]]
        if n == 0:
            diag = maindiag                        
            tilesfrompos = diag[0:pos[1]] 
        
        try:
            last1 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(1)
            last2 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(2)
            if tilesfrompos[-1] == 0 or tilesfrompos[-1] == who:
                return []
        except ValueError or IndexError:
            return []
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i > last1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i > last2]    
  
        for el in indices2:     
            if(who == 1 and set(tilesfrompos[last1+1:]) == {2}) or (who == 2 and set(tilesfrompos[last2+1:]) == {1}):
                if pos[0] > pos[1]:
                    pieces.append((el + 8 - len(diag),el))#EL IS THE COLUMN HERE
                if pos[0] < pos[1]:
                    pieces.append((el,el + 8 - len(diag))) #EL IS THE ROW HERE
                if diag == maindiag:
                    pieces.append((el,el))
                    
    if dir == (1,1):        
        
        if pos[0] > pos[1]:
            diag = lowerdiagonals[n-1]                      
            tilesfrompos = diag[pos[1]+1:] 
        if pos[0] < pos[1]:
            diag = upperdiagonals[n-1]
            tilesfrompos = diag[pos[0]+1:]
        if n==0:
            diag = maindiag
            tilesfrompos = diag[pos[0]+1:]
        try:
            first1 = tilesfrompos.index(1)
            first2 = tilesfrompos.index(2)
            if tilesfrompos[0] == 0 or tilesfrompos[0] == who: return []
        except ValueError or IndexError: return []
        
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i < first1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i < first2] 

        for el in indices2:               
            if(who == 1 and set(tilesfrompos[0:first1]) == {2}) or (who == 2 and set(tilesfrompos[0:first2]) == {1}):
                if pos[0] > pos[1]:
                    pieces.append((el + 8 - len(tilesfrompos),(el + len(diag)-len(tilesfrompos)))) #COL IS CORRECT
                if pos[0] < pos[1]:
                    pieces.append((el+len(diag)-len(tilesfrompos), el + 8 - len(tilesfrompos)))
                if diag == maindiag:
                    pieces.append((el+len(diag)-len(tilesfrompos),el+len(diag)-len(tilesfrompos)))
                    
                    
               
    for n in range(8):
        lowerdiagonals2.append(list(np.diag(np.fliplr(board),-n)))
        upperdiagonals2.append(list(np.diag(np.fliplr(board),n)))            
    maindiag2 = upperdiagonals2[0]
    del upperdiagonals2[0]
    del lowerdiagonals2[0]           
    n = abs(pos[0]-pos[1])
    k = pos[0] + pos[1]
    
    
    if dir == (-1,1):   
        
        if pos[0] + pos[1] < 7:
            diag = upperdiagonals2[6-k]             
            tilesfrompos = diag[0:pos[0]]
        if pos[0] + pos[1] > 7:
            diag = lowerdiagonals2[::-1][14-k]
            tilesfrompos = diag[0:7-pos[1]]
        if pos[0] + pos[1] == 7:
            diag = maindiag2
            tilesfrompos = diag[0:pos[0]] 
                 
        try:
            last1 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(1)
            last2 = len(tilesfrompos) - 1 - tilesfrompos[::-1].index(2)
            if tilesfrompos[-1] == 0 or tilesfrompos[-1] == who:
                return []
        except ValueError or IndexError:
            return []
        
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i > last1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i > last2] 
        
        cols = []
        rows = []
        for l in range(1,len(indices2)+1):
            cols.append(pos[1]+l)     
        for el in indices2:    
            if (who == 1 and set(tilesfrompos[last1+1:]) == {2}) or (who == 2 and set(tilesfrompos[last2+1:]) == {1}):
                if diag == upperdiagonals2[6-k]:
                    rows.append(el)
                for n in range(1,len(indices2)+1):                                                  
                    if pos[0] + pos[1] > 7:
                        rows.append(pos[0]-n)                         
                if diag == maindiag2:
                    rows.append(el)
        
        if pos[0] + pos[1] <= 7:                                      
            pieces = list(zip(rows[::-1], cols))
        if pos[0] + pos[1] > 7:
            pieces = list(zip(rows, cols))
    
    if dir == (1,-1):
        if pos[0] + pos[1] < 7:
            diag = (upperdiagonals2[::-1][k])                
            tilesfrompos = diag[pos[0]+1:] 
        if pos[0] + pos[1] > 7:
            diag = lowerdiagonals2[::-1][14-k]
            tilesfrompos = diag[8-pos[1]:] 
        if pos[0] + pos[1] == 7:
            diag = maindiag2
            tilesfrompos = diag[pos[0]+1:] 
        
            
        try:
            first1 = tilesfrompos.index(1)
            first2 = tilesfrompos.index(2)
            if tilesfrompos[0] == 0 or tilesfrompos[0] == who:
                return []
        except ValueError or IndexError:
            return []
    
        if who == 1:
            indices = [i for i, x in enumerate(tilesfrompos) if x == 2] # positions of all opponents pieces from 'pos' 
            indices2 = [i for i in indices if i < first1]
        else : 
            indices = [i for i, x in enumerate(tilesfrompos) if x == 1]
            indices2 = [i for i in indices if i < first2]
        cols = []
        rows = []
        for l in range(1,len(indices2)+1):
            cols.append(pos[1]-l)           
        for n in range(1,len(indices2)+1):    
            if(who == 1 and set(tilesfrompos[0:first1]) == {2}) or (who == 2 and set(tilesfrompos[0:first2]) == {1}):
                rows.append(pos[0]+n)        
        pieces = list(zip(rows, cols))
    
    if dir == (0,0):
        return []

    return pieces

def getValidMoves(board,who):
    """
    
    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there 
    who : Has the value 1 or 2 dependent on if it is player 1's or player 2's turn respectively
    
    Returns
    -------
    validpositions : A list of all the valid moves on the game-board 'board'. A valid move is a position that is 
    not occupied by either player from which there exists a continuous line of opponents pieces that ends with a piece
    of the current player. If the player 'who' has no valid moves, then validpositions will be empty. 
    
    """
    emptypositions = []
    validpositions = []
    directions = [(1,1),(-1,1),(1,0),(0,1),(0,-1),(-1,-1),(1,-1),(-1,0)]
    for n,l in itertools.product(range(8), range(8)):                
        if board[n][l] == 0: # gets all empty tiles
            emptypositions.append((n,l))   
    if who == 1 or who == 2:   
        for pos, dir in itertools.product(emptypositions, directions):                     
            if getLine(board,who,pos,dir) != []: # check if the empty position is a valid move 
                validpositions.append(pos)                   
        validpositions = list(set(validpositions)) # makes all elements in list only have 1 occurence
        
    return validpositions   



def makeMove(board,move,who):
    """
    Allows the players to make their selected move.

    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there
    move : A tuple of the form (m,k) that represents a position on the board where:
            ~ m is a number from 0 to 7 corresponding to the row on the board
            ~ k is a number from 0 to 7 corresponding to the column on the board
    who : Has the value 1 or 2 dependent on if it is player 1's or player 2's turn respectively
    
    Returns
    -------
    board : The updated board where the position on the board 'move' has been changed from 0 to the value of 'who'
    Also, all of the opponents pieces in a continuous straight line that starts from the position 'move' and ends with a piece
    of the current player 'who' are changed to the value 'who'.

    """
    tilestochange1 = []
    tilestochange2 = []
    board[move[0]][move[1]] = who  # change chosen position to that players number  
    directions = [(1,1),(-1,1),(1,0),(0,1),(0,-1),(-1,-1),(1,-1),(-1,0)]
    
    for dir in directions: 
        if getLine(board,who,move,dir) != []:
            tilestochange1.append(getLine(board,who,move,dir)) # finds all tiles that would change in all directions after move made
    
    for sublist in tilestochange1:
        for el in sublist:
            tilestochange2.append(el) # takes each element out of its sublist into one list
    

    for el in tilestochange2:
        board[el[0]][el[1]] = who # changes all relevant positions to that players number 
    return board     



def scoreBoard(board):
    """
    Scores the board.
    
    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there
    
    Returns
    -------
    Returns the integer that corresponds to the score of the board; calculated by counting how many tiles player 1 
    has and subracting how many tiles player 2 on the board. If it is greater than 0, player 1 is winning. If it is 
    less than 0, player 2 is winning. If it is equal to 0, the game is a draw.

    """
    alltiles =[]
    for n,k in itertools.product(range(8), range(8)): 

            alltiles.append(board[n][k]) # collects every single number on the board
    return (alltiles.count(1)-alltiles.count(2)) #counts each 1 and 2 and scores the board


def suggestMove1(board,who):
    """
    A simple AI opponent.
    
    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there
    who : Has the value 1 or 2 dependent on if it is player 1's or player 2's turn respectively.
    
    Returns
    -------
    Returns a random element from a list 'bestmoves' which contains moves that when made will give the player 'who'
    the best possible score for that particular board.
 
    """
    scores = []
    bestmoves = []
    validmoves = getValidMoves(board,who)

    if who == 1:  
        for move in validmoves:  
            scores.append(scoreBoard(makeMove(deepcopy(board),move,who))) # calculates score of each board after every valid move is made
        for move in validmoves:
            if scoreBoard(makeMove(deepcopy(board),move,who)) == max(scores): # finds move that made the board with the highest score
                bestmoves.append(move)
      
      
    if who == 2:
        for move in validmoves:  
            scores.append(scoreBoard(makeMove(deepcopy(board),move,who)))
        for move in validmoves:
            if scoreBoard(makeMove(deepcopy(board),move,who)) == min(scores):
                bestmoves.append(move)
                
       
   
    return(random.choice(bestmoves)) 
    
def suggestMove2(board,who):
    """
    An improved AI opponent.

    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there 
    who : Has the value 1 or 2 dependent on if it is player 1's or player 2's turn respectively.
    
    Returns
    -------
    A tuple that corresponds to a position on the board which will be one of the following: 
        ~ A corner piece if it is a valid move 
        ~ If a corner piece is not available: an edge piece if it is a valid move
        ~ If neither of the above are valid: a piece that reduces the opponents number of valid moves
    
    """
    
    bestmoves = []
    edges = []
    corners = []
    validmoves = getValidMoves(board,who)
    scores = []
    badpieces = []
    stable = []
    reallybadpieces = []
    setups = []
    boards1 = []
    boards2 = []
    moves1 = []
    moves2 = []
    

    if who == 1:  
        for move in validmoves:  
            boards1.append(makeMove(deepcopy(board),move,1))
            for boards in boards1:
                moves1.append(len(getValidMoves(boards,2)))
            if len(getValidMoves(makeMove(deepcopy(board),move,1),2)) == min(moves1):
                bestmoves.append(move)

            else:
                scores.append(scoreBoard(makeMove(deepcopy(board),move,who)))
                if scoreBoard(makeMove(deepcopy(board),move,who)) == min(scores):# find move which gives other player more tiles
                    bestmoves.append(move)
     
    if who == 2:
        for move in validmoves:  
            boards2.append(makeMove(deepcopy(board),move,2))
            for boards in boards2:
                moves2.append(len(getValidMoves(boards,1)))
            if len(getValidMoves(makeMove(deepcopy(board),move,2),1)) == min(moves2):
                bestmoves.append(move)
                
            else:
                scores.append(scoreBoard(makeMove(deepcopy(board),move,who)))
                if scoreBoard(makeMove(deepcopy(board),move,who)) == max(scores):
                    bestmoves.append(move)    
    
    for move in validmoves:
        if move[0] == 0 or move[0] == 7 or move[1] == 0 or move[1] == 7: # if move is an edge piece
            edges.append(move)
    
    if (0,1) in validmoves and (board[0][0] != who or board[0][7] != who):     
        badpieces.append((0,1))
    if (1,0) in validmoves and (board[0][0] != who or board[7][0] != who): 
        badpieces.append((1,0))
    if (1,1) in validmoves and board[0][0] != who:  
        badpieces.append((1,1))
    if (0,6) in validmoves and (board[0][0] != who or board[0][7] != who): 
        badpieces.append((0,6))
    if (1,6) in validmoves and board[0][7] != who: 
        badpieces.append((1,6))
    if (1,7) in validmoves and (board[7][7] != who or board[0][7] != who):
        badpieces.append((1,7))
    if (6,0) in validmoves and (board[0][0] != who or board[7][0] != who):
        badpieces.append((6,0))
    if (6,1) in validmoves and board[7][0] != who: 
        badpieces.append((6,1))
    if (7,1) in validmoves and (board[7][0] != who or board[7][7] != who): 
        badpieces.append((7,1))
    if (6,6) in validmoves and board[7][7] != who: 
        badpieces.append((6,6))
    if (6,7) in validmoves and (board[7][7] != who or board[0][7] != who):
        badpieces.append((6,7))
    if (7,6) in validmoves and (board[7][0] != who or board[7][7] != who): 
        badpieces.append((7,6))
    
    if (0,1) in validmoves and board[0][0] == who:     
        stable.append((0,1))
    if (1,0) in validmoves and board[0][0] == who:
        stable.append((1,0))
    if (1,1) in validmoves and board[0][0] == who:  
        stable.append((1,1))
    if (0,6) in validmoves and board[0][7] == who: 
        stable.append((0,6))
    if (1,6) in validmoves and board[0][7] == who: 
        stable.append((1,6))
    if (1,7) in validmoves and board[0][7] == who:
        stable.append((1,7))
    if (6,0) in validmoves and board[7][0] == who:
        stable.append((6,0))
    if (6,1) in validmoves and board[7][0] == who: 
        stable.append((6,1))
    if (7,1) in validmoves and board[7][0] == who: 
        stable.append((7,1))
    if (6,6) in validmoves and board[7][7] == who: 
        stable.append((6,6))
    if (6,7) in validmoves and board[7][7] == who:
        stable.append((6,7))
    if (7,6) in validmoves and board[7][7] == who: 
        stable.append((7,6))
    
    for el in validmoves:
        newboard = makeMove(deepcopy(board),el,who)
        if who == 1:
            if (0,0) or (0,7) or (7,7) or (7,0) in getValidMoves(newboard,2):
                reallybadpieces.append(el)
        if who == 2:
            if (0,0) or (0,7) or (7,7) or (7,0) in getValidMoves(newboard,1):
                reallybadpieces.append(el)

    for el in validmoves:
        newboard = makeMove(deepcopy(board),el,who)
        if (0,0) or (0,7) or (7,7) or (7,0) in getValidMoves(newboard,who):
            setups.append(el)
    
    for el in badpieces or reallybadpieces:
        if el in edges: 
            edges.remove(el)
        if el in bestmoves:            
            bestmoves.remove(el)
    for el in reallybadpieces:
        if el in badpieces:
            badpieces.remove(el)
        if el in setups: 
            setups.remove(el)


    for move in validmoves:
        if move == (0,0) or move == (0,7) or move == (7,7) or move == (7,0): # if move is a corner piece
            corners.append(move) 

            
    if corners != []:
        return(random.choice(corners))
    elif stable != []:
        return(random.choice(stable))
    elif setups != []:
        for el in setups:
            newboard = makeMove(deepcopy(board),el,who)
            if who == 1:                            
                if len(getValidMoves(newboard,2)) < len(getValidMoves(board,2)): # if move makes other player have less valid moves 
                    return el
                else: 
                    return(random.choice(setups))
            if who == 2:
                if len(getValidMoves(newboard,1)) < len(getValidMoves(board,1)):
                    return el
                else:
                    return(random.choice(setups))
    elif bestmoves != []:
        return(random.choice(bestmoves))

        
    elif edges != []:       
        for el in edges:
            newboard = makeMove(deepcopy(board),el,who)
            if who == 1:                            
                if len(getValidMoves(newboard,2)) < len(getValidMoves(board,2)): # if move makes other player have less valid moves 
                    return el
                else: 
                    return(random.choice(edges))
            if who == 2:
                if len(getValidMoves(newboard,1)) < len(getValidMoves(board,1)):
                    return el
                else:
                    return(random.choice(edges))
                                
    
    elif badpieces != []:
        return(random.choice(badpieces))
    elif reallybadpieces != []:
        return(random.choice(reallybadpieces))
        
        
        
def suggestMove3(board,who):
    """
    An improved AI opponent.

    Parameters
    ----------
    board : List of 8 lists that makes up the game board. The elements in each list is either: 
        ~ 0 if no player is positioned there
        ~ 1 if player 1 is positioned there
        ~ 2 if player 2 is positioned there 
    who : Has the value 1 or 2 dependent on if it is player 1's or player 2's turn respectively.
    
    Returns
    -------
    A tuple that corresponds to a position on the board which will be one of the following: 
        ~ A corner piece if it is a valid move 
        ~ If a corner piece is not available: an edge piece if it is a valid move
        ~ If neither of the above are valid: a piece that reduces the opponents number of valid moves
    
    """
    
    bestmoves = []
    edges = []
    corners = []
    validmoves = getValidMoves(board,who)
    scores = []
    badpieces = []
    stable = []
    reallybadpieces = []
    setups = []

    if who == 1:  
        for move in validmoves:  
            newboard = makeMove(deepcopy(board),move,1)
            if len(getValidMoves(newboard,2)) < len(getValidMoves(board,2)): # if move makes other player have less valid moves 
                bestmoves.append(move)
            else:
                scores.append(scoreBoard(makeMove(deepcopy(board),move,who)))
                if scoreBoard(makeMove(deepcopy(board),move,who)) == min(scores):# find move which gives other player more tiles
                    bestmoves.append(move)
     
    if who == 2:
        for move in validmoves:  
            newboard = makeMove(deepcopy(board),move,2)
            if len(getValidMoves(newboard,1)) < len(getValidMoves(board,1)): # if move makes other player have less valid moves 
                bestmoves.append(move)
            else:
                scores.append(scoreBoard(makeMove(deepcopy(board),move,who)))
                if scoreBoard(makeMove(deepcopy(board),move,who)) == max(scores):
                    bestmoves.append(move)    
    
    for move in validmoves:
        if move[0] == 0 or move[0] == 7 or move[1] == 0 or move[1] == 7: # if move is an edge piece
            edges.append(move)
    
    if (0,1) in validmoves and (board[0][0] != who or board[0][7] != who):     
        badpieces.append((0,1))
    if (1,0) in validmoves and (board[0][0] != who or board[7][0] != who): 
        badpieces.append((1,0))
    if (1,1) in validmoves and board[0][0] != who:  
        badpieces.append((1,1))
    if (0,6) in validmoves and (board[0][0] != who or board[0][7] != who): 
        badpieces.append((0,6))
    if (1,6) in validmoves and board[0][7] != who: 
        badpieces.append((1,6))
    if (1,7) in validmoves and (board[7][7] != who or board[0][7] != who):
        badpieces.append((1,7))
    if (6,0) in validmoves and (board[0][0] != who or board[7][0] != who):
        badpieces.append((6,0))
    if (6,1) in validmoves and board[7][0] != who: 
        badpieces.append((6,1))
    if (7,1) in validmoves and (board[7][0] != who or board[7][7] != who): 
        badpieces.append((7,1))
    if (6,6) in validmoves and board[7][7] != who: 
        badpieces.append((6,6))
    if (6,7) in validmoves and (board[7][7] != who or board[0][7] != who):
        badpieces.append((6,7))
    if (7,6) in validmoves and (board[7][0] != who or board[7][7] != who): 
        badpieces.append((7,6))
    
    if (0,1) in validmoves and board[0][0] == who:     
        stable.append((0,1))
    if (1,0) in validmoves and board[0][0] == who:
        stable.append((1,0))
    if (1,1) in validmoves and board[0][0] == who:  
        stable.append((1,1))
    if (0,6) in validmoves and board[0][7] == who: 
        stable.append((0,6))
    if (1,6) in validmoves and board[0][7] == who: 
        stable.append((1,6))
    if (1,7) in validmoves and board[0][7] == who:
        stable.append((1,7))
    if (6,0) in validmoves and board[7][0] == who:
        stable.append((6,0))
    if (6,1) in validmoves and board[7][0] == who: 
        stable.append((6,1))
    if (7,1) in validmoves and board[7][0] == who: 
        stable.append((7,1))
    if (6,6) in validmoves and board[7][7] == who: 
        stable.append((6,6))
    if (6,7) in validmoves and board[7][7] == who:
        stable.append((6,7))
    if (7,6) in validmoves and board[7][7] == who: 
        stable.append((7,6))
    
    for el in validmoves:
        newboard = makeMove(deepcopy(board),el,who)
        if who == 1:
            if (0,0) or (0,7) or (7,7) or (7,0) in getValidMoves(newboard,2):
                reallybadpieces.append(el)
        if who == 2:
            if (0,0) or (0,7) or (7,7) or (7,0) in getValidMoves(newboard,1):
                reallybadpieces.append(el)

    for el in validmoves:
        newboard = makeMove(deepcopy(board),el,who)
        if (0,0) or (0,7) or (7,7) or (7,0) in getValidMoves(newboard,who):
            setups.append(el)
    
    for el in badpieces or reallybadpieces:
        if el in edges: 
            edges.remove(el)
        if el in bestmoves:            
            bestmoves.remove(el)
    for el in reallybadpieces:
        if el in badpieces:
            badpieces.remove(el)
        if el in setups: 
            setups.remove(el)


    for move in validmoves:
        if move == (0,0) or move == (0,7) or move == (7,7) or move == (7,0): # if move is a corner piece
            corners.append(move) 

            
    if corners != []:
        return(random.choice(corners))
    elif stable != []:
        return(random.choice(stable))
    elif setups != []:
        for el in setups:
            newboard = makeMove(deepcopy(board),el,who)
            if who == 1:                            
                if len(getValidMoves(newboard,2)) < len(getValidMoves(board,2)): # if move makes other player have less valid moves 
                    return el
                else: 
                    return(random.choice(setups))
            if who == 2:
                if len(getValidMoves(newboard,1)) < len(getValidMoves(board,1)):
                    return el
                else:
                    return(random.choice(setups))

        
    elif edges != []:       
        for el in edges:
            newboard = makeMove(deepcopy(board),el,who)
            if who == 1:                            
                if len(getValidMoves(newboard,2)) < len(getValidMoves(board,2)): # if move makes other player have less valid moves 
                    return el
                else: 
                    return(random.choice(edges))
            if who == 2:
                if len(getValidMoves(newboard,1)) < len(getValidMoves(board,1)):
                    return el
                else:
                    return(random.choice(edges))
                                
    elif bestmoves != []:
        return(random.choice(bestmoves))
    elif badpieces != []:
        return(random.choice(badpieces))
    elif reallybadpieces != []:
        return(random.choice(reallybadpieces))
        
        



# ------------------- Main function --------------------
def play():
    """
    Contains the flow of the game. 
    """

    print("*"*55)
    print("***"+" "*8+"WELCOME TO JOSH'S OTHELLO GAME!"+" "*8+"***") 
    print("*"*55,"\n")
    print("Enter the players' names, or type 'C' (computer), 'C2' (improved computer) or 'L' (load a game file).\n")
    player1 = input("Enter the name of player 1: ").capitalize() # capitalizes player name
    while player1 == '':  # ensures name is not empty
        print('Name cannot be empty!')
        player1 = input("Enter the name of player 1: ").capitalize()

    if player1 == 'L':
        print('Game loaded')
        gamedict = loadGame() # loads game dictionary 
        player1 = gamedict['player1'] # assigns the players names from the dictionary
        player2 = gamedict['player2']
        
       
    else: 
        player2 = input("Enter the name of player 2: ").capitalize()
        while player2 == '':
            print('Name cannot be empty!')
            player2 = input("Enter the name of player 2: ").capitalize()
        gamedict = newGame(player1,player2) # loads new game dictionary
        
   
    who = int(gamedict['who']) # decides whose turn it is and the current board from the game dictionary
    board = gamedict['board'] 
    printBoard(board)   
    while getValidMoves(board,1) != [] or getValidMoves(board,2) != []:
        
        if who == 1:
                        
            if getValidMoves(board,1) == []:
                print(player1 + ' (X) you have no valid moves! So it is ' + player2 + "'s (O) turn.")
                who = 2
            
            if who == 1:
                if player1 == 'C':   # computer makes move
                    move = suggestMove1(board,who)
                    print('The computer (X) has decided to move to .... ' + str(indexToStr(move)))
                  
                if player1 == 'C2': # improved computer makes move
                    move = suggestMove2(board,who)
                    print('The computer (X) has decided to move to .... ' + str(indexToStr(move)))
                   
                
                if player1 != 'C' and player1 != 'C2':       
                    move = strToIndex(input(player1 + ' (X) enter your move: '))   # player inputs their move 
                    while (move in getValidMoves(board,who)) == False: # if move invalid
                        print('\nInvalid Move')
                        move = strToIndex(input(player1 + ' enter your move: '))            
                makeMove(board,move,who)  # make the move
                printBoard(board)   # print the board in nice format          
                who = 2   # switch players turn

        
        
        
        if who == 2: 
            
            
            if getValidMoves(board,2) == []:
                print(player2 + ' (O) you have no valid moves! So it is ' + player1 + "'s (X) turn.")
                who = 1
            
            if who == 2:            
                
                if player2 == 'C':
                    move = suggestMove3(board,who)
                    print('The computer (O) has decided to move to .... ' + str(indexToStr(move)))
                    
                if player2 == 'C2':
                    move = suggestMove2(board,who)
                    print('The computer (O) has decided to move to .... ' + str(indexToStr(move)))
                    
                 
                
                if player2 != 'C' and player2 != 'C2':                         
                    move = strToIndex(input(player2 + ' (O) enter your move: '))         
                    while (move in getValidMoves(board,who)) == False:
                        print('\nInvalid Move')
                        move = strToIndex(input(player2 + ' enter your move: '))            
                makeMove(board,move,who)
                printBoard(board)
                who = 1
        
    
            

    if getValidMoves(board,1) == [] and getValidMoves(board,2) == []: # end of the game
        print('No valid moves left for either player, so the game is over!')
        score = scoreBoard(board)
        if score == 0:
            print('The game is a draw!')
        
         
        if score > 0:
            print('The score is: ' + str(score))     # decides the winner
            print(player1 + ' (X) is the winner!')
            
         
        if score < 0:
            print('The score is: ' + str(score))
            print(player2 + ' (O) is the winner!')
           
           
            
          
   

        
    
              
                
    # the following allows your module to be run as a program
if __name__ == '__main__' or __name__ == 'builtins': play()